package solution.design;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-10-18 9:44
 * 设计题目：895. 最大频率栈
 * 实现 FreqStack，模拟类似栈的数据结构的操作的一个类。
 */
public class FreqStack {
    // 记录 FreqStack 中元素的最大频率
    int maxFreq=0;
    // 记录 FreqStack 中每个 val 对应的出现频率，后文就称为 VF 表
    HashMap<Integer,Integer> valToFreq=new HashMap<>();
    // 记录频率 freq 对应的 val 列表，后文就称为 FV 表
    HashMap<Integer, Stack<Integer>>freqToVals=new HashMap<>();


    public FreqStack() {
    }

    //将整数 x 推入栈中。
    public void push(int val) {
        //修改vk
        int freq = valToFreq.getOrDefault(val, 0) + 1;
        valToFreq.put(val,freq);
        //修改fV表
        freqToVals.putIfAbsent(freq,new Stack<>());
        freqToVals.get(freq).push(val);
        //更新maxFreq
        maxFreq=Math.max(maxFreq,freq);
    }

    //它移除并返回栈中出现最频繁的元素。如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。
    public int pop() {
        //修改FV表，pop出一个maxFreq的元素
        Stack<Integer> stack = freqToVals.get(maxFreq);
        Integer val = stack.pop();
        //修改vk表
        Integer freq = valToFreq.get(val)-1;
        valToFreq.put(val,freq);
        //更新maxFreq
        if (stack.isEmpty()){
            //maxfreq对应的元素为空了
            maxFreq--;
        }
        return val;
    }
}
